package max.tree.avl;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import max.Algorithm;
import max.tree.avl.AVLTree.AVLTreeMap;

public class NlognVsNN {
	/**
	 * 小数据 <br>
	 * 不短路 hashmap nlogn nn <br>
	 * 短路 nn hashmap nlogn <br>
	 * 大数据 <br>
	 * hashmap <br>
	 * 综上，建议选择哈希表 <br>
	 * @param args
	 */
	public static void main(String[] args) {
		// 不print情况下
		// 运行时间：nlogn算法，n^2算法
		// 10个 常数项影响较大
		// 程序运行时间： 5167500ns 6ms,程序运行时间： 10300ns 0ms
		// 100个 常数项影响比较大
		// 程序运行时间： 9929000ns 10ms,程序运行时间： 96000ns 0ms
		// 1000 左右不分伯仲
		// 程序运行时间： 14345600ns 14ms，程序运行时间： 25174500ns 25ms
		// 10万 优势明显
		// 程序运行时间： 215613300ns 216ms，程序运行时间： 3751026300ns 3750ms
		// 100w 高低立现
		// 程序运行时间： 1956534200ns 1956ms ,程序运行时间： 378720547700ns 378721ms
		int[] array = new int[] { 0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 1 };
		int size = 100;
		boolean print = false;
		array = Algorithm.createRandomArray(size, size * 10);
//		Algorithm.printArray(array);
		System.out.println("--准备完成数组");
//		long startTime = System.nanoTime();// 获取开始时间.nanoTime();
//		long startTime1 = System.currentTimeMillis();// 获取开始时间.nanoTime();
//		p1(array, print);
//		long endTime = System.nanoTime(); // 获取结束时间
//		long endTime1 = System.currentTimeMillis(); // 获取结束时间
//		System.out.println("--");
//		System.out.println("程序运行时间： " + (endTime - startTime) + "ns " + (endTime1 - startTime1) + "ms");
//		System.out.println("--");
//		startTime = System.nanoTime(); // 获取开始时间
//		startTime1 = System.currentTimeMillis(); // 获取开始时间
//		p2(array, print);
//		endTime = System.nanoTime(); // 获取结束时间
//		endTime1 = System.currentTimeMillis(); // 获取结束时间
//		System.out.println("--");
//		System.out.println("程序运行时间： " + (endTime - startTime) + "ns " + (endTime1 - startTime1) + "ms");
//		System.out.println("--");

		Algorithm.time(array, (a) -> {
			p1(a, print);
		});

		Algorithm.time(array, (a) -> {
			p2(a, print);
		});

		Algorithm.time(array, (a) -> {
			p3(a, print);
		});

	}

	public static void p1(int[] array, boolean b) {
		AVLTreeMap atm = new AVLTreeMap();
		for (int element : array) {
			Object a = atm.put(element, null, null);
//			if(a!=null) {
			// System.out.println(a);
//				return;
//			}
		}
		atm.getNodeSizeUp2(b);
	}

	public static void p2(int[] array, boolean b) {
		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = array.length - 1; j > i; j--) {
				if (array[i] == array[j]) {
//					if (b) {
//						System.out.print(array[i] + ",");
//					}
//					return;
					set.add(i);
				}
			}
		}
	}

	public static void p3(int[] array, boolean b) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int element : array) {
			if (map.containsKey(element)) {
				map.put(element, map.get(element) + 1);
			} else {
				map.put(element, 1);
			}
		}
		for(Entry<Integer,Integer> entry : map.entrySet()) {
			if(entry.getValue()>1) {
				//System.out.print(entry.getKey()+",");
			}
		}
	}

	public static int getDuplicate(int[] arr) {
		if (arr == null || arr.length <= 0) {
			System.out.println("数组输入无效！");
			return -1;
		}
		for (int a : arr) {
			if (a < 0 || a > arr.length - 1) {
				System.out.println("数字大小超出范围！");
				return -1;
			}
		}
		for (int i = 0; i < arr.length; i++) {
			int temp;
			while (arr[i] != i) {
				if (arr[arr[i]] == arr[i])
					return arr[i];
				// 交换arr[arr[i]]和arr[i]
				temp = arr[i];
				arr[i] = arr[temp];
				arr[temp] = temp;
			}
		}
		System.out.println("数组中无重复数字！");
		return -1;
	}
}
